package org.example.myleet.p689;

public class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        //记录三个不重叠数组在找到新的最大的和的时候的开头
        int i1 = 0, i2 = k, i3 = 2 * k;
        //记录第一个子数组找到新的更大的和的时候的开头
        int mi1 = i1;
        //三个数组的和并初始化
        int s1 = 0, s2 = 0, s3 = 0;
        for (int i = 0; i < k; ++i) {
            s1 += nums[i];
        }
        for (int i = k; i < 2 * k; ++i) {
            s2 += nums[i];
        }
        for (int i = 2 * k; i < 3 * k; ++i) {
            s3 += nums[i];
        }
        //s1的最大和
        int maxSum1 = s1;
        //s1和s2的最大和
        int maxSum12 = maxSum1 + s2;
        //s1和s2和s3的最大和
        int maxSum123 = maxSum12 + s3;
        int[] result = new int[]{i1, i2, i3};
        for (int i = 3 * k; i < nums.length; ++i) {
            //滑动窗口
            s3 += nums[i];
            s3 -= nums[i - k];
            s2 += nums[i - k];
            s2 -= nums[i - 2 * k];
            s1 += nums[i - 2 * k];
            s1 -= nums[i - 3 * k];
            if (s1 > maxSum1) {
                //子数组1找到更大的位置，刷新子数组1的最大开始位置
                maxSum1 = s1;
                mi1 = i - 3 * k + 1;
            }
            if (maxSum1 + s2 > maxSum12) {
                //子数组2找到更大的位置，刷新子数组1和子数组2的最大开始位置
                maxSum12 = maxSum1 + s2;
                i1 = mi1;
                i2 = i - 2 * k + 1;
            }
            if (maxSum12 + s3 > maxSum123) {
                //子数组3找到更大的位置，刷新子数组1和子数组2和子数组3的最大开始位置，并更新到结果中
                maxSum123 = maxSum12 + s3;
                i3 = i - k + 1;
                result[0] = i1;
                result[1] = i2;
                result[2] = i3;
            }
        }
        return result;
    }
}
